import Queue from "@/sources/Queue/useDcl";
import Stack from "@/sources/Stack/useSl";
import { assert } from "console";
import { Tree } from "../base";
import { IIterator } from "./types";

// 二叉树节点定义
export class BstNode<T = number> {
    value: T | undefined
    left: BstNode<T> | null
    right: BstNode<T> | null
    parent: BstNode<T> | null
    constructor(value: T, parent: BstNode<T> | null, left: BstNode<T> | null, right: BstNode<T> | null) {
        this.value = value;
        this.parent = parent
        this.left = left;
        this.right = right;
    }
    /**
     * p的右孩子
     * @param p 
     */
    isRight() {
        if (this.parent === null) return false
        return this.parent.right === this
    }

    /**
     * p的左孩子
     * @param p 
     */
    isLeft() {
        if (this.parent === null) return false
        return this.parent.left === this;
    }

    /**
     * 是不是叶子节点
     */
    isLeaf() {
        return this.left == null && this.right == null
    }

    /**
     * 是不是根节点
     */
    isRoot() {
        return this.parent === null
    }

    /**
     * 节点度为2
     */
    hasTwoChild() {
        return this.left !== null && this.right !== null
    }

    /**
     * 节点度为1
     */
    hasOneChild() {
        return (this.left === null && this.right !== null) || (this.left !== null && this.right === null)
    }

    /**
     * 是否有右孩子
     */
    hasRightChild() {
        return this.right !== null
    }

    /**
     * 是否右左孩子
     */
    hasLeftChild() {
        return this.left !== null
    }

}

/**
 * 二叉搜索树
 */
export default class BST<T> extends Tree<T> {
    private sizes = 0;
    private root: BstNode<T> | null
    private stop: boolean = false
    // 默认的比较器
    private comparator = (a: T, b: T) => ((a as any) - (b as any))
    constructor(comparator?: (a: T, b: T) => number) {
        super();
        this.root = null
        comparator && (this.comparator = comparator);
    }

    /**
     * 获取根节点
     */
    getRoot() {
        return this.root;
    }

    /**
     * 节点的数量
     */
    size() {
        return this.sizes;
    }

    /**
     * 是否为空
     */
    isEmpty() {
        return this.sizes === 0
    }

    /**
     * 清空二叉树
     */
    clear() {
        // 清空根节点和sizes置为空即可
        this.sizes = 0;
        this.root = null
    }

    /**
     * 添加节点
     * @param element 
     */
    add(element: T) {
        // 首次添加
        if (this.root === null) {
            this.root = new BstNode(element, null, null, null);
            this.sizes++;
            return;
        }

        // 找到要插入的节点
        let root = this.root;
        let prevNode: BstNode<T> | null,
            isRight = false;
        while (root) {
            // 保存这次的节点
            prevNode = root;
            if (this.comparator(element, root.value!) > 0) {
                // 往右边找
                root = root.right!;
                isRight = true
            } else if (this.comparator(element, root.value!) < 0) {
                // 往左边找
                root = root.left!
                isRight = false;
            } else {
                // 相等，直接更新节点的值
                root.value = element
                // 直接返回
                return;
            }
        }

        // 到这prevNode就是要找的插入的节点
        // 判断插入左还是右
        if (isRight) {
            // 插入 prevNode的右边
            prevNode!.right = new BstNode(element, prevNode!, null, null)
        } else {
            // 插入prevNode的左边
            prevNode!.left = new BstNode(element, prevNode!, null, null)
        }

        this.sizes++;
    }


    /**
     * 获取element
     * @param element 
     */
    private get(element: T) {
        let root = this.root!;
        while (root !== null) {
            if (this.comparator(element, root.value!) > 0) {
                root = root.right!;
            } else if (this.comparator(element, root.value!) < 0) {
                root = root.left!;
            } else {
                // 找到了
                return root
            }
        }
        // 循环下来都没有找到
        return null
    }

    /**
     * 删除节点
     * @param element 
     */
    remove(element: T) {
        let node = this.get(element);
        // 要删除的节点不存在
        if (node === null) return null

        // 删除度为2的节点, 找到其前驱或者后继节点， 这里使用前驱节点
        if (node.hasTwoChild()) {
            // 1. 获取node节点的前驱节点
            const accesssor = this.accessor(node);

            // 2. 使用前驱节点替换要删除的该节点
            node.value = accesssor!.value

            // 3. 删除该前驱节点, 跟删除度为1和度为2的节点一样
            node = accesssor
        }

        // 判断该节点是父元素的左孩子还是右孩子
        const isLeft = node!.isLeft() ? true : false
        // 删除度为1的节点
        if (node?.hasOneChild()) {
            // 节点的孩子是左还是右
            const hasLeftChild = node.hasLeftChild();
            // 找到替换的节点
            const replacement = (hasLeftChild ? node.left : node.right)!;

            // 该节点是跟节点
            if (node.parent == null) {
                this.root = replacement
            } else {
                if (isLeft) {
                    node.parent!.left = replacement
                } else {
                    node.parent!.right = replacement
                }
            }
            // 更新父节点
            replacement.parent = node.parent
        } else if (node!.parent === null) {
            // 删除的是根节点
            this.root = null
        } else {
            // 度为0的节点
            if (isLeft) {
                // 是父节点的左孩子
                node!.parent!.left = null
            } else {
                // 是父节点的右孩子
                node!.parent!.right = null
            }
        }
        // 长度减一
        this.sizes--;

    }

    /**
     * 后继节点
     * 从根节点的右节点开始，不断找该右节点的左节点
     */
    successor(root: BstNode<T>) {
        // 树是空的
        if (this.isEmpty()) return null;
        let node = root?.right;
        // 没有右节点
        if (node === null) return null;

        while (node!.left !== null) {
            node = node?.left;
        }
        return node;
    }

    /**
     * 前继节点
     * 从根节点的左节点开始，不断找该左节点的右节点
     */
    accessor(root: BstNode<T>) {
        if (this.isEmpty()) return null;
        let node = root?.left;
        // 没有左节点
        if (node === null) return null;

        while (node!.right !== null) {
            node = node?.right;
        }
        return node;
    }


    /**
     * 是否包含元素
     * @param element 
     */
    contains(element: T) {
        if (this.isEmpty()) return false
        return this.get(element) !== null;
    }

    /**
     * 批量添加
     * @param eles 
     */
    batchAdd(eles: Array<T>) {
        eles.forEach(ele => {
            this.add(ele)
        })
    }

    /**
     * 求树的高度, 没传节点默认是root
     */
    height(n?: T) {
        // 空树
        if (this.isEmpty()) return 0
        const root = this.get(n || this.root!.value!)
        // 所传的值对应的节点不存在
        if (root === null) {
            console.warn('所传的值对应的节点不存在');
            return 0
        }
        // 创建队列
        const queue = new Queue<BstNode<T>>();
        queue.enQueue(root);

        // size减为0代表当前层数已经访问完毕了
        let levelSize = 1,
            height = 0;
        // 默认根先入队
        while (!queue.isEmpty()) {
            const node = queue.deQueue();
            // 每访问一次node, levelSize就要--
            levelSize--

            // 左子树存在，左子树入队
            if (node.left) {
                queue.enQueue(node.left)
            }

            // 右子树存在，右子树入队
            if (node.right) {
                queue.enQueue(node.right)
            }

            // size变为0
            if (levelSize === 0) {
                // 重置levelSize
                levelSize = queue.size();

                // 高度加1
                height++;
            }
        }
        return height;
    }


    /**
     * 使用数组代替队列
     * @param n 
     */
    heightUseArr(n?: T) {
        // 空树
        if (this.isEmpty()) return 0
        const root = this.get(n || this.root!.value!)
        // 所传的值对应的节点不存在
        if (root === null) {
            console.warn('所传的值对应的节点不存在');
            return 0
        }
        // 创建队列
        const queue: Array<BstNode<T>> = [];
        queue.push(root);

        // size减为0代表当前层数已经访问完毕了
        let levelSize = 1,
            height = 0;
        // 默认根先入队
        while (queue.length) {
            // 从头取
            const node = queue.shift()!;
            // 每访问一次node, levelSize就要--
            levelSize--

            // 左子树存在，左子树入队
            if (node.left) {
                queue.push(node.left)
            }

            // 右子树存在，右子树入队
            if (node.right) {
                queue.push(node.right)
            }

            // size变为0
            if (levelSize === 0) {
                // 重置levelSize
                levelSize = queue.length;

                // 高度加1
                height++;
            }
        }
        return height;
    }

    /**
     * 递归的先序遍历
     */
    preOrder(node = this.root, iterator: IIterator<T> = v => true) {
        // 重置stop
        if (node === this.root) this.stop = false
        if (node === null || this.stop === true) return
        // 遍历当前的节点
        this.stop = iterator(node.value!)
        // if (this.stop) return;
        // 遍历左子节点
        this.preOrder(node.left, iterator)
        // 遍历右子节点
        this.preOrder(node.right, iterator);
    }

    /**
     * 中序遍历
     * @param node 
     */
    inOrder(node = this.root, iterator: IIterator<T> = v => true) {
        // 重置stop
        if (node === this.root) this.stop = false

        if (node === null || this.stop) return;

        // 遍历左子节点
        this.inOrder(node.left, iterator)

        // 访问当前节点
        this.stop = iterator(node.value!)


        // 遍历右子节点
        this.inOrder(node.right, iterator)
    }

    /**
     * 后序遍历
     * @param node 
     */
    postOrder(node = this.root, iterator: IIterator<T> = v => true) {
        // 重置stop
        if (node === this.root) this.stop = false
        if (node === null || this.stop) return;

        // 遍历左子节点
        this.postOrder(node.left, iterator);

        // 遍历右子节点
        this.postOrder(node.right, iterator);

        // 访问当前节点
        this.stop = iterator(node.value!)
    }

    /**
     * 前序遍历(非递归)
     * @param node 
     */
    preOrderIterator(node = this.root, iterator: IIterator<T> = v => true) {
        if (node === null) return;
        // 创建一个栈
        const stack = new Stack<BstNode<T>>();
        stack.push(node)
        while (!stack.isEmpty()) {
            // 最左边节点为空了, 开始从栈弹出之前压入右节点
            node = stack.pop()!;

            // 从该节点开始，一直访问左子节点
            while (node !== null) {
                // 访问当前节点
                if (iterator(node.value!)) return
                // 将右节点压入栈中
                if (node.right !== null) {
                    stack.push(node.right);
                }
                // 指向左子节点
                node = node.left;
            }
        }

    }

    /**
     * 中序遍历(非递归)
     * @param node 
     */
    inOrderIterator(node = this.root, iterator: IIterator<T> = v => true) {
        if (node === null) return;
        // 创建一个栈
        const stack = new Stack<BstNode<T>>()

        // 1. 开始时node为根节点，进入循环
        // 2. 最左节点为空，栈中还有值
        // 3. 栈为空了，开始遍历右边
        while (node === this.root || !stack.isEmpty() || node !== null) {
            // 从node开始一直遍历到最左边
            while (node !== null) {
                stack.push(node);
                node = node.left;
            }
            // 最左边为空， 开始取出最左边的节点开始访问
            node = stack.pop()!;

            // 访问节点
            if (iterator(node.value!)) return

            // 访问节点的右节点
            node = node.right;
        }
    }

    /**
     * 后序遍历(非递归)
     * @param node 
     */
    postOrderIterator(node = this.root, iterator: IIterator<T> = v => true) {
        if (node === null) return;
        const stack = new Stack<BstNode<T>>();
        let prevNode: any = null
        stack.push(node)
        while (!stack.isEmpty()) {
            const top = stack.top()!;

            // 有右孩子并且上一个弹出的节点的父亲不是top
            if (top.right !== null && prevNode?.parent !== top) {
                // 将右孩子压入栈中
                stack.push(top.right);
            }

            // 有左孩子并且上一个弹出的节点的父亲不是top
            if (top.left !== null && prevNode?.parent !== top) {
                stack.push(top.left)
            }

            // 左右孩子都为空 或者之前已经将其孩子访问过了
            if ((top.right === null && top.left === null) || prevNode?.parent === top) {
                // 左右都为空，开始访问节点
                const node = stack.pop()!;
                prevNode = node;
                // 访问节点
                if (iterator(node.value!)) return
            }
        }
    }


    /**
     * 求树的深度
     */
    depth(n?: T) {
        // 深度就是高度-1
        return this.height(n) - 1
    }

    /**
     * 判断该树是不是二叉树
     */
    isComplete() {
        const root = this.root;
        if (root === null) return false
        const queue = new Queue<BstNode<T>>()
        queue.enQueue(root!);
        let hasOne = false
        while (!queue.isEmpty()) {
            // 出队
            const node = queue.deQueue();

            // 只有一个节点
            if (node.hasOneChild()) {
                // 之前已经有一个节点，这次还有一个，完全二叉树不可能右两个度为1的节点 
                if (hasOne) return false
                hasOne = true

                // 一度的节点，但是是右节点
                if (node.hasRightChild()) return false
            }

            // 有右子节点
            if (node.right !== null) queue.enQueue(node.right)

            // 有左子节点
            if (node.left !== null) queue.enQueue(node.left)
        }

        return true
    }

    /**
     * 拷贝一个和root一样的二叉树
     */
    copy() {
        let root = this.root;

        // 根节点是空的
        if (root === null) return null;

        // 创建一个新的根 
        const newRoot = new BstNode<T>(root.value!, null, null, null)

        /**
         * 拷贝二叉树
         * @param o 旧节点
         * @param n 新节点
         */
        const copy = (o: BstNode<T>, n: BstNode<T>) => {
            // debugger
            if (o.left) {
                // 右左孩子, 拷贝左孩子
                n.left = new BstNode(o.left.value!, n, null, null)

                // 递归拷贝左孩子
                copy(o.left, n.left);
            }

            if (o.right) {
                // 有右孩子, 拷贝右孩子
                n.right = new BstNode(o.right.value!, o, null, null)

                // 递归拷贝右孩子
                copy(o.right, n.right)
            }
        }   
        copy(root, newRoot)

        return newRoot;
    }
} 